package code2101_2200.code60_70;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
 *
 * 示例:
 *
 * 现有矩阵 matrix 如下
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * 给定 target = 5，返回 true。
 *
 * 给定 target = 20，返回 false。
 */
public class _2161findNumberIn2DArray {

    /**
     *
     * 没想到直接二分查找的效率这么高！。本来还准备优化一下呢。 此处按照题解方法复述一遍
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 44 MB     * , 在所有 Java 提交中击败了     * 76.86%     * 的用户
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0)return false;
        for (int i = 0; i < matrix.length; i++) {
            int index = devide(matrix[i],target);
            if(matrix[i][index] == target){
                return true;
            }
        }
        return false;
    }

    /**
     * 二分法找最接近target的下标，或者直接找到下标
     * @param nums
     * @param target
     * @return
     */
    public int devide(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int mid;
        while (left<right){
            mid = left+(right-left)/2;
            if(nums[mid]>target){
                right = mid - 1;
            }else if(nums[mid]<target){
                left = mid + 1;
            }else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 题解方法：类似于matris[0][0]为根节点的二叉树
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 44 MB     * , 在所有 Java 提交中击败了     * 80.54%     * 的用户
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }

}
